package demo1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-07-20
 * Time: 11:28
 */
public class HashBuck {
    static class Node{
        public int val;
        public int key;
        public Node next;
        public Node (int val , int key ){
            this.val = val;
            this.key = key;
        }
    }

    public Node[] array;//数组里存放的是地址不是具体的数据
    public int usedsize;//存放的节点个数。也就是数据个数

    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //对数组进行初始化
    //构造方法
    public HashBuck(){
        array = new Node[10];//数组的各个位置后面加链表

    }//数组的每一个格子放的是一个节点
    //hash冲突
    public void put(int key , int val){
        //第一步先确定要插入的位置
        int index = key % array.length;
        Node cur = array[index];
        //第二步
        //遍历数组下标下的链表中是否存在  关键字key ，若存在更新key，若不存在进行尾插法
        while (cur != null ){ //遍历数组
            if (cur.key == key){
                cur.val = val;
            }
            cur = cur.next;
        }

        //第三步：头插法
        //在链表中没有找到关键字key
        //头插法实例化一个节点
        Node node = new Node(val,key);
        node.next = array[index];//不要钻牛角尖，理解很重要，☆这里的array[index]赋值是把array[index]所存储的node的地址赋值给node.next
        array[index] = node;
        usedsize++;
        if (doLoadFactor() > 0.75){
            //负载因子的调节，扩容
            //array = Arrays.copyOf(array , array.length*2);
            // 不能这么扩容，链表中的元素可能会存在位置的变动，原来位置冲突的元素可能要放到新的数组的位置上去
            //需要重新hash一下
            resize();

        }
    }


    private float doLoadFactor(){
        return usedsize * 1.0f / array.length;
    }
/*
* 扩容方法*/
    public void resize(){
        //第一步扩容
        Node[] newArray = new Node[array.length*2];


        //第二步：遍历原来的数组的每一个元素
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];  //先从左往右走数组

            //第三步：遍历链表
            while(cur != null){ //在判断非空
                int newindex = cur.key % newArray.length;//在确定新的下标，这里如果新下标和原来的下标相同了，current.next不就指向自己了嘛

                //第四步：调整链表（关键的一步，先绑定后面再绑定前面）
                Node temp = cur.next;//修改之前记录下来
                cur.next = newArray[newindex];//解决了，创建的新数组中元素并没有拷贝过去的，所以cur.next = null了，只是画图软件上没有直接表现出来
                newArray[newindex] = cur;
                //(error)cur = cur.next;指向变了，要先用中间变量存储一下
                cur = temp;
            }
        }
        array = newArray;

    }

    public int get(int key){
        int index = key % array.length;
        Node cur = array[index];
        //遍历数组下标下的链表中是否存在  关键字key ，若存在更新key
        while (cur != null ){
            if (cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }




}
